
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2023. -- [Usaco2005 Oct]Flying Right -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2023: [Usaco2005 Oct]Flying Right</h2><span class=green>Time Limit: </span>4 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>13&nbsp;&nbsp;<span class=green>Solved: </span>8<br>[<a href='submitpage.php?id=2023'>Submit</a>][<a href='problemstatus.php?id=2023'>Status</a>][<a href='bbs.php?id=2023'>Discuss</a>]</center><h2>Description</h2><div class=content>
Figuring that they cannot do worse than the humans have, Farmer
John's cows have decided to start an airline.  Being cows, they
decide to cater to the heretofore-untapped market of cows as
passengers. They plan to serve the cows who live along the western
coast of Lake Michigan. Each morning, they will fly from the
northern-most point of the coast southward towards Chicowgo, making
many stops along the way.  Each evening, they will fly back north
to the northern-most point.

They need your help to decide which passengers to carry each day.
Each of N (1 <= N <= 10,000) farms numbered 1..N along the coast
contains an airport (Farm 1 is northern-most; farm N is southern-most).
On this day, K (1 <= K <= 50,000) groups of cows wish to travel.
Each group of cows wants to fly from a particular farm to another
particular farm.  The airline, if it wishes, is allowed to stop and
pick up only part of a group. Cows that start a flight, however,
must stay on the plane until they reach their destination.

Given the capacity C (1 <= C <= 100) of the airplane and the groups
of cows that want to travel, determine the maximum number of cows
that the airline can fly to their destination.


约翰的奶牛们开通了一条飞机航线，专门为奶牛服务。每天早上，她们沿着密歇根湖的西岸，从线路的最北端出发飞到最南端，全程经过N个机场（包括头尾两个）。到了下午，她们又会沿着同样的路线飞回最北端。每天都会有数目不同的K群奶牛要求乘坐飞机，一群牛会在某一个机场等待，并希望飞到另外一个特定的机场。
飞机上只能同时容纳C头奶牛乘客，航班的负责牛希望知道在这一天中她们最多可以满足多少头奶牛的要求。飞机可以只将一群牛中的一部分带到目的地。
约定：1≤N≤10,000，1≤K≤50,000，1≤C≤100。
</div><h2>Input</h2><div class=content>
* Line 1: Three space-separated integers: K, N, and C

* Lines 2..K+1: Each line contains three space-separated integers S,
        E, and M that specify a group of cows that wishes to travel. 
        The M (1 <= M <= C) cows are currently at farm S and want to
        travel to farm E (S != E).
</div><h2>Output</h2><div class=content>
* Line 1: The maximum number of cows that can be flown to their
        destination. This is the sum of the number of cows flown to
        their destination on the flight southward in the morning plus
        the number of cows flown to their destination on the flight
        northward in the evening.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
4 8 3<br />
1 3 2<br />
2 8 3<br />
4 7 1<br />
8 3 2<br />
<br />
INPUT DETAILS:<br />
<br />
Four groups of cows, eight farms, and three seats on the<br />
plane.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
6<br />
<br />
OUTPUT DETAILS:<br />
<br />
In the morning, the flight takes 2 cows from 1->3, 1 cow from 2->8,<br />
and 1 cow from 4->7.  In the evening, the flight takes 2 cows from<br />
8->3.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2023'>Submit</a>][<a href='problemstatus.php?id=2023'>Status</a>][<a href='bbs.php?id=2023'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
